package LeetCode.LC114;

/**
 * @author corn
 * @create 2020-07-31-16:00
 */

/**
 * 114. 二叉树展开为链表
 *
 * 给定一个二叉树，原地将它展开为一个单链表。
 */
public class Flatten {

}
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
class Solution {
    public void flatten(TreeNode root) {
        if(root == null ){
            return;
        }
        move(root,root.left,root.right);
    }
    public void move(TreeNode root,TreeNode left,TreeNode right){
        //左子树为 null，直接考虑下一个节点
        if(left == null){
            if(right == null){
                return;
            }else {
                move(root.right, root.right.left, root.right.right);
            }
        }else{
            // 将左子树插入到右子树的地方
            root.right = left;
            // 找左子树最右边的节点
            TreeNode node = root.right;
            while (node.right != null){
                node = node.right;
            }
            //将原来的右子树接到左子树的最右边节点
            node.right = right;
            //将左子树设置为空
            root.left = null;
            move(root.right, root.right.left, root.right.right);
        }

    }
}
